/*
题目链接:https://leetcode.cn/problems/count-good-numbers/submissions/621908850/?envType=daily-question&envId=2025-04-13
*/

//题解代码:

class Solution {
public:
    #define ll long long
    const int mod = 1e9+7;
    ll power(ll a,ll b){
        ll ret = 1;
        while(b){
            if(b&1) ret = (ret * a) % mod;
            a = (a * a) % mod;
            b>>=1;
        }
        return ret;
    }
    int countGoodNumbers(long long n) {
        return power(4,n/2) * power(5,(n+1)/2) % mod;
    }
};
